Improvements in computer technology have provided computing devices with the capability to render realistic graphical images. The improvements have been due, in large part, to the development of computer monitors capable of rendering images with near-photographic resolution and to the continued growth of processing power that allows high-resolution images to be manipulated at acceptable speeds. As a result, computing devices are now able to process and display motion videos, such as movies and action video games.
Images generated by the computing device are displayed on a pixel-oriented display device, typically a computer monitor. The term "monitor" typically refers to the video display and its housing. The monitor's video display is typically a cathode ray tube (CRT), although other video displays may include a liquid crystal display (LCD) or any other type of display capable of rendering images visible to the user. The CRT has a phosphor layer on the inner surface of the front of the tube. The outer surface of the tube, i.e., the surface facing the viewer of the monitor on which the images are displayed, is typically called the "computer screen".
A computer screen displays graphical and other images by illuminating picture elements on the CRT. A picture element, or "pixel", is the smallest area of a computer screen that can be manipulated to create an image. In a color monitor, each pixel comprises an element for each of the primary colors red, green, and blue. By varying the intensity of the three elements, a pixel can display nearly any desired color.
Each pixel on the computer screen is identified by its location on the screen and can be illuminated at varying levels of brightness and at various colors. Colors are displayed on the computer screen in connection with a palletized graphics device or a non-palletized graphics device. In a non-palletized device, a pixel value for each pixel on the screen encodes the color at which each respective pixel is to be displayed. For example, in an eight bit red, green, blue (RGB) color system, the pixel value includes each color component as a value of 0-255. As is well known in the art, a pixel value of (255, 0, 0) constitutes the color red, (0, 255, 0) constitutes the color green, and (0, 0, 255) constitutes the color blue. Similarly, black is identified by the pixel value (0, 0, 0), white is identified by (255,255,255). A pixel value of (127, 0, 127) identifies dark purple because the red and blue components are half intensity and there is no green component.
In a palletized device, the pixel value for each pixel is an index into an array of colors. The array of colors is called the palette. Typically, in an eight bit system, palettes have 256 entries, numbered from 0-255, but may include more or fewer entries. For example, a pixel value of 10 means that the pixel is displayed using color number 10 in the palette.
As is well known in the art, the display of each pixel on the computer screen can be manipulated by the computer system. One of the graphical effects used by computer systems is the "dissolve" effect. A dissolve occurs when an image on the screen (the current image) is replaced, pixel by pixel, with another image (the source image). Thus, the dissolve effect is accomplished by dissolving the image by progressively replacing each pixel of a current image with a corresponding pixel of a source image until the current image is no longer displayed and the source image is completely displayed.
With computer systems today having increasingly elaborate graphics and audio capabilities, many possibilities exist for making computer programs more interesting and entertaining for the user. To create and display a dissolve effect that is visually pleasing to the viewer, the order in which pixels of a current image are replaced with pixels of a source image should appear to be random. A random order of pixel replacement creates what appears to be a smooth fade or transition. If the order in which pixels are replaced on the screen during the dissolve effect is not random, undesirable, visually-recognizable patterns are displayed. For example, if a fixed pattern of pixels are replaced on the screen during the dissolve effect, such as alternating pixels or the first pixel of every five contiguous pixels in a row, a "checkerboard" or "striping" effect is displayed. These effects are visually displeasing.
Additionally, each pixel in the current image that is replaced on the screen should not be replaced again during the dissolve sequence. Thus, each pixel should be replaced on the screen only one time during the dissolve sequence. For example, if a pixel of the current image that has been replaced with a pixel of the source image is replaced again with the pixel of the current image, then the pixel must again be replaced with the pixel of the source image to complete the dissolve sequence. Such mulitple replacements of pixels produces a visually undesirable "sparkling" effect.
Many computer programs that provide dissolve effects do not determine the replacement of pixels in a seemingly random order. Therefore, many of the prior implementations of dissolve effects include undesirable visual effects during the dissolve sequence. Additionally, because any determination of a random order of pixels is potentially expensive in terms of the processing time required of the computing device, any system for providing such-a seemingly random order of pixels should require a minimum of processor time.